//
// Created by liushuai on 18-8-26.
//

#include "Graph_Travel.hpp"
#include <iostream>
#include <vector>
#include <memory.h>
Graph_Travel::Graph_Travel(int capacity) {
    Capacity = capacity;
    NodeCount = 0;
    NodeArray = new Node[Capacity];
    adj_Matrix = new int[Capacity*Capacity];
    memset(adj_Matrix,0,Capacity*Capacity* sizeof(int));
//    memset(adj_Matrix,0,Capacity*Capacity*sizeof(int));

}

Graph_Travel::~Graph_Travel() {
    delete [] NodeArray;
    delete [] adj_Matrix;
}
bool Graph_Travel::addNode(Node *pNode) {
    if(pNode == nullptr)
        return false;
    NodeArray[NodeCount].Data = pNode->Data;
    NodeCount++;
    return true;
}
void Graph_Travel::resetNode() {
    for(int i=1;i<NodeCount;i++)
        NodeArray[i].IsVisited = false;
}
bool Graph_Travel::setValueToMatrixForDirectedGraph(int row, int col, int val) {
    if(row<0||row>=Capacity)
        return  false;
    else if(col<0&&col>=Capacity)
        return false;
    else
    {
        NodeArray[row*Capacity+col] = val;
        return true;
    }

}
bool Graph_Travel::setValueToMatrixUndirectedGraph(int row, int col, int val) {
    if(row<0||row>=Capacity)
        return  false;
    else if(col<0&&col>=Capacity)
        return false;
    else
    {
        adj_Matrix[row*Capacity+col] = val;
        adj_Matrix[col*Capacity+row] = val;
        return true;
    }

}
void Graph_Travel::printMatrix() {
    for(int i=0;i<Capacity;i++)
    {
        for(int k=0;k<Capacity;k++)
        {
            std::cout<<adj_Matrix[i*Capacity+k]<<" ";
        }
        std::cout<<"\n";
    }
}
bool Graph_Travel::getValueFromMatrix(int row, int col, int &val) {
    if(row<0||row>=Capacity)
        return  false;
    else if(col<0&&col>=Capacity)
        return false;
    else
    {
        val = adj_Matrix[row*Capacity+col];
        return true;
    }
}
void Graph_Travel::DFS(int nodeIndex) {
    int value = 0;
    std::cout<<NodeArray[nodeIndex].Data<<" ";
    NodeArray[nodeIndex].IsVisited = true;
    for(int i = 0;i<Capacity;i++)
    {
        getValueFromMatrix(nodeIndex,i,value);
        if(value == 1)
        {
            if(NodeArray[i].IsVisited)
                continue;
            else
                DFS(i);
        }
        else
        {
            continue;
        }
    }
}
void Graph_Travel::BFS(int nodeIndex) {
    std::cout<<NodeArray[nodeIndex].Data<<" ";
    NodeArray[nodeIndex].IsVisited = true;
    std::vector<int> cuVec;
    cuVec.push_back(nodeIndex);
    breadthFirstTraverseImp(cuVec);
}
void Graph_Travel::breadthFirstTraverseImp(std::vector<int> preVec) {
    int value = 0;
    std::vector<int> curVec;
    for(int j=0;j<(int)preVec.size();j++)
    {
        for(int i=0;i<Capacity;i++)
        {
            getValueFromMatrix(preVec[j],i,value);
            if(value!=0)
            {
                if(NodeArray[i].IsVisited)
                    continue;
                else
                {
                    std::cout<<NodeArray[i].Data<<" ";
                    NodeArray[i].IsVisited = true;
                    curVec.push_back(i);
                }
            }

        }

    }
    if(curVec.size() == 0)
        return;
    else
        breadthFirstTraverseImp(curVec);
}





















